package utils.hash;

/**
 * <p>MurmurHash3 算法由Austin Appleby创建，并进行开源。这个 java 端口最初由 Yonik Seeley 编写，也进行了开源。作者特此声明对该源代码的版权，本人在此基础上稍作修改。</p>
 * <p>该代码产生的哈希与 MurmurHash3 的最终 C++ 版本完全相同的哈希值，因此适合于跨平台产生相同的哈希。</p>
 * <p>该哈希的 32 位 x86 版本应该是 ID 等相对较短密钥的最快变体。对于较长的字符串，或者如果你需要 32 位以上的哈希值，dummuh ash3_x64_128 是一个不错的选择。</p>
 * <p>注意 -x86 和 x64 版本不会产生相同的结果，因为算法针对各自的平台进行了优化。</p>
 * <p>Murmurhash 指的就是 multiply 和 rotate,组成 murmur ，即乘和旋转两个操作，但是实际上还有 xor 异或操作在名字中没有体现</p>
 */
public final class MurmurHash3 {

    MurmurHash3() {
    }

    /**
     * 计算 x86 系统的 32 位 Murmurhash
     *
     * @param data   待编码数据
     * @param offset 起始位置
     * @param len    数据长度，即 key 的长度
     * @param seed   随机数种子
     * @return int 值
     */
    public static int murmurhash3_x86_32(byte[] data, int offset, int len, int seed) {
        /* 这些常量在运算的时候会用到，至于为什么是这些值，这是前辈们在大量测验中（卡方测试和雪崩测试）发现，下面这些值效果是很好的 */
        final int c1 = 0xcc9e2d51; // 3,432,918,353
        final int c2 = 0x1b873593; // 461,845,907
        final int c3 = 0x85ebca6b; // 2,246,822,507
        final int c4 = 0xc2b2ae35; // 3,266,489,909
        // 用于左移和右移
        final int rotl1 = 15;
        final int rotr1 = 17; // 15 + 17 = 32
        final int rotl2 = 13;
        final int rotr2 = 19; // 13 + 19 = 32
        final int m = 5;
        final int n = 0xe6546b64; //3,864,292,196

        int h1 = seed; // 这是一个随机数
        // 0xfffffffc = 0b1111_1111_1111_1111_1111_1111_1111_1100
        // len & 0xfffffffc 实际上就是清除 len 的最后两个比特位
        // 这个作用就是将 len 转成 4 的倍数，用于进行下面的 4 字节分组（int 是四个字节）
        // 为什么是 4 的倍数呢，因为 1100 = 12, 1000 = 8, 0100 = 4, 0000 = 0，自然就可以构成 4 的倍数
        // 如果最后冗余出来一些比特位，例如 4 mod 9 = 1，这 1 个比特位作为剩余数据进行处理
        int roundedEnd = offset + (len & 0xfffffffc);
        // 第一步，分组求解
        for (int i = offset; i < roundedEnd; i += 4) {
            // & 0xff 即取得最后一个字节，如果一个数为一个字节，那么 & 0xff 后其值不变
            // & 0xff 单字节操作时多用于基本类型和字节的转换
            // k1 由高到低四个位分别是 data[i + 3] data[i + 2] data[i + 1] data[i]
            int k1 = (data[i] & 0xff)
                    | ((data[i + 1] & 0xff) << 8)
                    | ((data[i + 2] & 0xff) << 16)
                    | ((data[i + 3] & 0xff) << 24);
            k1 *= c1;
            k1 = (k1 << rotl1) | (k1 >>> rotr1); //
            k1 *= c2;
            h1 ^= k1;
            h1 = (h1 << rotl2) | (h1 >>> rotr2); //
            h1 = h1 * m + n;
        }
        int k1 = 0;
        // 0x03 = 0b0000_0011
        // 第二步，这里是处理剩余数据，本质就是数据倒置
        int s = len & 0x03;
        switch (s) {
            case 3:
                k1 = (data[roundedEnd + 2] & 0xff) << 16;
            case 2:
                k1 |= (data[roundedEnd + 1] & 0xff) << 8;
            case 1:
                k1 |= (data[roundedEnd] & 0xff);
                k1 *= c1;
                k1 = (k1 << rotl1) | (k1 >>> rotr1);
                k1 *= c2;
                h1 ^= k1;
            default:
                break;
        }
        // 结束
        h1 ^= len;

        // 最后一步作用是强化通过雪崩测试，加强输入敏感性，下面的常量内容都是经验值
        h1 ^= h1 >>> 16;
        h1 *= c3;
        h1 ^= h1 >>> 13;
        h1 *= c4;
        h1 ^= h1 >>> 16;

        return h1;
    }
}
